// https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 递归计算二叉树的最大深度
// 2. 空节点深度为0，叶子节点深度为1
// 3. 左右子树深度取最大值加1得到当前深度
// 4. 深度优先搜索遍历所有节点
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int maxDepth(TreeNode* root) 
    {
        if (root == nullptr)
        {
            return 0;
        }

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return max(leftDepth, rightDepth) + 1;
    }
};

int main()
{
    vector<string> tree1 = {"3","9","20","null","null","15","7"};
    vector<string> tree2 = {"1","null","2"};

    Solution sol;

    auto root1 = buildTree(tree1);
    auto root2 = buildTree(tree2);

    cout << sol.maxDepth(root1) << endl;
    cout << sol.maxDepth(root2) << endl;

    return 0;
}